#include <iostream>
#include "bst.h"

template<class type>
BinaryTree<type>::BinaryTree() {
        pRoot = NULL;
        pLinearArray = NULL;
        arrayCount = 0;
}

template<class type>
BinaryTree<type>::~BinaryTree() {
        destroy(pRoot);
        if( pLinearArray != NULL)
        {
                delete[] pLinearArray;
        }
}

template<class type>
void BinaryTree<type>::insertNode(type data) {
        insert(pRoot , data);
}

template<class type>
void BinaryTree<type>::insert(node<type>*& pNode , type data) {
        if(pNode == NULL) {
                pNode = new node<type>(data , NULL , NULL);  
        }
        else if( data < pNode->data) {
                insert(pNode->pLeft , data);
        }
        else {
                insert(pNode->pRight , data);
        }
}

/**
 * 데이터를 보고 node를 찾아서 지우기 때문에 searching을 함께한다.
 * searching 부분과 찾은 target을 실제로 지우는 부분을 구분하는 것이 더 좋겠다.
 *
 * @param data                  data to be deleted from BST.
 * @return                      void.
 */
template<class type>
void BinaryTree<type>::deleteNode(type data) {
        deleteThis(pRoot , data);
}

template<class type>
void BinaryTree<type>::deleteThis(node<type>*& pNode, type data) {
        if( data.xValue < pNode->data.xValue ) {
                deleteThis(pNode->pLeft , data);
        }
        else if(data.xValue > pNode->data.xValue) {
                deleteThis(pNode->pRight , data);
        }
        else {
                deleteThisNode(pNode);
        }
}

template<class type>
void BinaryTree<type>::GetPredecessor(node<type>* pNode , type& data) {
        while( pNode->pRight != NULL)
        {
                pNode = pNode->pRight;
                data = pNode->data;
        }
}

/**
 * node를 삭제하는 실제 함수
 *
 * r이 leaf이면 그냥 삭제
 * r의 자식이 하나만 있으면 r의 부모가 r의 자식을 직접 가리키도록 수정
 *
 */
template<class type>
void BinaryTree<type>::deleteThisNode(node<type>*& pNode) {
        type data;
        node* pTemp;
        pTemp = pNode;
        if(pNode->pLeft == NULL) {
                pNode = pNode->pRight;
                delete pTemp;
        }
        else if( pNode->pRight == NULL) {
                pNode = pNode->pLeft;
                delete pTemp;
        }
        else {
                this->GetPredecessor(pNode->pLeft , data);
                pNode->data = data;
                deleteThis(pNode->pLeft , data);
        }
}

template<class type>
void BinaryTree<type>::findData(type& data , int& isFound) {
        find(pRoot , data , isFound);
}

template<class type>
void BinaryTree<type>::find(node<type>* pNode , type& data , int& isFound) {
        if(pNode == NULL) {
                isFound = -1;
        }
        else if( data.xValue < pNode->data.xValue ) {
                find(pNode->pLeft , data , isFound);
        }
        else if( data.xValue > pNode->data.xValue ) {
                find(pNode->pRight , data , isFound);
        }
        else {
                data = pNode->data;
                isFound = 1;
        }
}

template<class type>
void BinaryTree<type>::print() {
        this->arrayCount = getCount();
        if(arrayCount > 0) {
                if(pLinearArray != NULL) {
                        delete[] pLinearArray;
                        pLinearArray = NULL;
                }
                this->pLinearArray = new type[arrayCount];
        }
        this->arrayCount = 0;
        printNode(pRoot);
}

template<class type>
void BinaryTree<type>::printNode(node<type>* pNode) {
        if(pNode != NULL) {
                printNode(pNode->pLeft);
                pLinearArray[arrayCount] = pNode->data;
                arrayCount++;
                printNode(pNode->pRight);
        }
}

template<class type>
int BinaryTree<type>::getCount() {
        return countNodes(pRoot);
}

template<class type>
int BinaryTree<type>::countNodes(node<type>* pNode) {
        if(pNode == NULL) {
                return 0;
        }
        else {
                return countNodes( pNode->pLeft ) + countNodes(pNode->pRight) + 1;
        }
}

template<class type>
void BinaryTree<type>::destroy(node<type>*& pNode) {
        if(pNode != NULL) {
                destroy(pNode->pLeft);
                destroy(pNode->pRight);
                delete pNode;
        }
}

template<class type>
void BinaryTree<type>::clearAll() {
        destroy(pRoot);
        pRoot = NULL;
        if(pLinearArray != NULL)
        {
                delete[] pLinearArray;
                pLinearArray = NULL;
        }
        arrayCount = 0;
}

template<class type>
int BinaryTree<type>::merge(BinaryTree<type>* merge , BinaryTree<type>* left , BinaryTree<type>* right , type data) {
        //합병트리의 루트에 자료 삽입
        merge->insertNode( data );
        merge->pRoot->pLeft = left->pRoot;
        merge->pRoot->pRight = right->pRoot;

        left->pRoot = NULL;
        right->pRoot = NULL;
        return 0;
}
